package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         130,
		Discription: "将被围绕的区域清除（边缘不算)",
		Level:       2,
		Labels: map[string]int{
			"矩阵": 1,
			"递归": 1,
			"中间态":1,
		},
	})
}

// 如果区域不被围绕但为'O'，置为‘A’，遍历完成后，将‘A’置为‘O’，将‘O’置为‘X’
// 只需遍历四条边上的O，找到与他们连接的‘O'，然后都置为’A‘
func Solve(board [][]byte) {
	m := len(board)
	n := len(board[0])
	if m <= 1 || n <= 1 {
		return
	}

	var dfs func(int, int)
	dfs = func(i int, j int) {
		if i < 0 || i >= m || j < 0 || j >= n {
			return
		}

		if board[i][j] != 'O' {
			return
		}

		board[i][j] = 'A'
		dfs(i-1, j)
		dfs(i+1, j)
		dfs(i, j-1)
		dfs(i, j+1)
	}

	//只需遍历四条边上的O，找到与他们连接的‘O'，然后都置为’A‘
	for i := 0; i <= m-1; i++ {
		dfs(i, 0)
		dfs(i, n-1)
	}
	for j := 1; j <= n-2; j++ {
		dfs(0, j)
		dfs(m-1, j)
	}

	for i := 0; i <= m-1; i++ {
		for j := 0; j <= n-1; j++ {
			if board[i][j] == 'O' {
				board[i][j] = 'X'
			} else if board[i][j] == 'A' {
				board[i][j] = 'O'
			}
		}
	}
}
